package _02_greedy_algorithm;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author: mornd
 * @dateTime: 2023/7/20 - 15:06
 * 活动选择问题（结论：按活动结束时间升序，即优先选择最先结束的活动，再比较开始时间是否冲突）
 */
public class ActivitySelectionProblem {
    class Activity {
        int index;
        int start;
        int finish;

        public Activity(int index, int start, int finish) {
            this.index = index;
            this.start = start;
            this.finish = finish;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Activity.class.getSimpleName() + "[", "]")
                    .add("index=" + index)
                    .add("start=" + start)
                    .add("finish=" + finish)
                    .toString();
        }
    }

    @Test
    public void test() {
        /*
            0   1   2   3   4   5   6
        0       |-------)                √
        1           |-------)
        2               |-------)        √

         */
        Activity[] activities = new Activity[]{
                new Activity(0, 1, 3),
                new Activity(1, 2, 4),
                new Activity(2, 3, 5),
        };

        List<Activity> result = select(activities);
        List<Activity> result2 = select2(activities);
        System.out.println(result);
        System.out.println(result2);
    }

    /**
     * 排序实现
     *
     * @param activities
     * @return
     */
    private List<Activity> select(Activity[] activities) {
        // 结束时间升序排列
        Arrays.sort(activities, Comparator.comparingInt(x -> x.finish));
        List<Activity> result = new ArrayList<>();
        // 首先选定一个最先结束的活动
        result.add(activities[0]);
        int index = activities[0].finish;

        for (int i = 1; i < activities.length; i++) {
            // 起始时间和上一个活动的结束时间比较
            if (activities[i].start >= index) {
                result.add(activities[i]);
                index = activities[i].finish;
            }
        }
        return result;
    }

    /**
     * 优先级队列实现
     *
     * @param activities
     * @return
     */
    private List<Activity> select2(Activity[] activities) {
        PriorityQueue<Activity> queue = new PriorityQueue<>(
                Comparator.comparingInt(x -> x.finish)
        );
        queue.addAll(Arrays.stream(activities).toList());

        List<Activity> result = new ArrayList<>();
        Activity first = queue.poll();
        result.add(first);
        int index = first.finish;

        while (!queue.isEmpty()) {
            Activity poll = queue.poll();
            if (poll.start >= index) {
                result.add(poll);
                index = poll.finish;
            }
        }
        return result;
    }
}
